package com.wrial.simple;
/*
 * @Author  Wrial
 * @Date Created in 10:44 2020/8/2
 * @Description
 * https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
 */

public class Offer_68_II二叉树的最近公共祖先 {

    /**
     * 可以使用递归，可以分为三种情况：
     * 1.两个节点在root的同侧（同左或同右）
     * 2.两个节点在root的异测
     * 3.一个节点在root，一个节点在左侧或者右侧
     *
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null || root == p || root == q) {//3
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null) return right;//1
        if (right == null) return left;//1
        return root;//left!=null && right!=null 0

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
